接雨水

题目介绍

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

传送门

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

思路

当然，这道题是用尺取法（two pointers）做的，当然大家都会这么做。但是本着不重复造轮子的想法，这里提供一个不同的解法，目标不是快，而是短，尝试提交最短的代码， 说起来，Scala就挺适合的，天生的巨量语法糖让一个Scala程序可以十分短。虽然C++是殿堂级的算法竞赛用到的语言，但是作为休闲玩家，可以尝试一些新的作死玩意儿。 因此这里提供一种Scala解，目前还是我最短（滑稽）。

首先我们看要如何才能确定容纳的水量，首先是要确定每一个位置的水位线，再将水位线之和减去柱子的高度和即可。

一个水位线是由在该位置向左和向右看所能到达的最高柱子，两者之间的较小的一个值决定的，换一句话说：

如果我将这个容器装满水，再向左转90°，有部分水流走了，剩下的水是被其向左的最高的柱子挡住的，因此流不下来，再向右也是同理。因此每个位置的两者的最小值就是当前的水位线。

那么答案也就呼之欲出了，从左向右扫描，记录每个位置之前的最大值，再从右往左重复相同的步骤，取这两个结果的较小值求和，再减去柱子的高度和就可以了。

背景函数介绍

接下来介绍用到的函数，大部分是height（Array[Int]）的成员函数：

• Array[T].scan(z: T)(f: (T, T) => T): 由一个初始值开始，从左向右，进行积累的op操作
• scanLeft 即scan
• scanRight 相反方向的scan

举例：

val nums = List(1,2,3)
val result = nums.scan(10)(_+_) 
//=>  List(10,10+1,10+1+2,10+1+2+3) = List(10,11,12,13)

• drop(n: Int): List[A] 丢弃前n个元素，返回剩下的元素
• dropRight: dropRight(n: Int): List[A] 丢弃最后n个元素，返回剩下的元素

def tupled[a1, a2, b](f: (a1, a2) => b): Tuple2[a1, a2] => b = {
    case Tuple2(x1, x2) => f(x1, x2)
  }

• Function.tupled将一个二元函数转换成一个接受一个二元组的函数
• zip: zip[B](that: GenIterable[B]): List[(A, B)] 与另外一个列表进行拉链操作，将对应位置的元素组成一个pair，返回的列表长度为两个列表中短的那个

List(1, 2, 3).zip(4, 5, 6) //= List((1, 4), (2, 5), (3, 6))

• sum 返回数组的元素和

代码

整体代码如下：

object Solution {
    def trap(height: Array[Int]): Int = 
      height.scan(0)(_ max _).drop(1)
      .zip(height.scanRight(0)(_ max _).dropRight(1))
      .map(Function.tupled(_ min _)).sum - height.sum
}

闲话

是不是很简洁？

当然你可以说这个代码虽然只有一行但是每一个函数做的事情用C艹都要写一卡车代码，我只能说naive，这才是Scala的魅力。